#!/usr/bin/env python
# encoding: utf-8
'''
@author: Excelsiorly
@license: (C) Copyright 2022, All Rights Reserved.
@contact: excelsiorly@qq.com
@file: 015. 三数之和.py
@time: 2022/1/6 13:05
@desc: https://leetcode-cn.com/problems/3sum/
> 给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。

@解题思路：
    1. 排序
    2. 从左到右选取1个元素i进行固定
    3. 在区间[i+1, n-1]区级设左右指针L、R
    4. 计算nums[i]+nums[L]+nums[R]的值：
            a. 若==0，则三者是符合条件的解，进行收录
            b. 若<0，则说明L处小了，应当右移左指针，选用更大的数字
            c. 若>0. 则说明R处大了，应当左移右指针，选用更小的数字
    5. t: O(N2), s: O(logN)
@难点：
    1. 重复解：
        - 当i与i-1相同，则遍历时会出现重复解，应当跳过
        - 当目前的i-L-R符合条件，则若L==L+1, R==R-1,都会导致重复解出现，也应检查跳过
        - 示例：[-1, -1, -1, 0, 1, 2]
'''
class Solution(object):
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        # 特例
        if not nums or len(nums)<3:
            return []
        res = []
        n = len(nums)
        # 排序
        nums.sort()
        for i in range(n):
            # 若当前数已经大于0，因已经排过序了，后面不会有负数让其和能等于0了，因此可以结束
            if nums[i]>0:
                return res
            # 避免重复项，比如[-1, -1, -1, 0, 1, 2]
            if i>0 and nums[i]==nums[i-1]:
                continue
            L, R = i+1, n-1
            while L<R:
                sum = nums[i]+nums[L]+nums[R]
                if sum==0:
                    res.append([nums[i], nums[L], nums[R]])
                    # 跳过重复性
                    while L<R and nums[L]==nums[L+1]:
                        L+=1
                    while L<R and nums[R]==nums[R-1]:
                        R -= 1
                    L += 1
                    R -= 1
                elif sum<0:
                    L += 1
                else:
                    R -= 1

        return res

class Solution02(object):
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        if not nums or len(nums)<3: return []
        n, res = len(nums), []
        nums.sort()

        # [-4, -1, -1, 0, 1, 2]
        for i in range(n):
            if nums[i]>0: return res
            if i>0 and nums[i]==nums[i-1]: continue
            L, R = i+1, n-1
            while L<R:
                sum = nums[i] + nums[L] + nums[R]
                if sum==0:
                    res.append([nums[i], nums[L], nums[R]])
                    # 去除重复项
                    while L < R and nums[L] == nums[L + 1]: L += 1
                    while L < R and nums[R] == nums[R - 1]: R -= 1
                    L += 1
                    R -= 1
                elif sum<0:
                    # 跳过重复项
                    L += 1
                else:
                    R -= 1
        return res

if __name__ == '__main__':
    res = Solution02().threeSum([-2,0,0,2,2])
    print(res)